package com.frx.datastruct.chapterfour;

/**
 * @author ：frx
 * @date ：Created in 2019/2/16 23:18
 * @description： 实现链表这种数据结构
 * @modified By：
 * @version: ToDO
 */
public class LinkedList<E> {

    /** 将节点设置为内部私有类*/
      private class Node{
          public E e;
          public Node next;

          public Node (E e,Node next){
              this.e = e;
              this.next = next;
          }

          public Node(E e){
              this(e,null);
          }

          public Node(){
              this(null,null);
          }

          @Override
        public String toString(){
              return e.toString();
          }
      }
      /** 设置链表的头节点  (使用虚拟头节点) 虚拟头节点的下一个节点为0所在的节点*/
      private Node dummyHead;
      private int size;

      public LinkedList(){
          dummyHead = new Node(null,null);
          size = 0;
      }
      /** 获得链表中元素个数 */
    public int getSize(){
          return size;
    }
    /** 判空 */
    public boolean isEmpty(){
          return size > 0;
    }

    /** 在链表中间添加元素  (索引为index的位置添加元素)
     * 插入元素的操作  原理就是先找到要插入位置的前一个节点prev
     * 然后将要插入的节点node,node.next指向prev.next,prev.next指向node
     * */
    public void add(int index,E e){
          if(index<0 || index>size){
              throw new IllegalArgumentException("Add Failed, illegal index.");
          }

              //指向虚拟头节点的指针  为了找到指向index的前一个位置，所以从虚拟 头节点处开始遍历
              Node prev = dummyHead;
              //遍历找到index前一个位置
              for (int i = 0; i<index;i++){
                  prev = prev.next;
              }
              //同上优雅的写法
              prev.next = new Node(e,prev.next);
              size++;

    }
    /** 在链表头添加新的元素*/
    public void addFirst(E e){
        //Node node = new Node(e);
        //node.next = head;
        //head = node;

        //比较优雅的写法
 /*       head = new Node(e,head);
        size++;*/

        //直接复用add()
        add(0,e);
    }
    /** 在链表末尾添加元素 */
    public void addLast(E e){
          //在索引为size的位置添加元素
        add(size,e);
    }

    /** 查找操作get() 获得链表的第index位置的元素*/
    public E get(int index){
          //首先判断参数合法性
        if(index<0 || index > size){
            throw new IllegalArgumentException("Get failed. Illegal Index!");
        }
        // 进行遍历，主要是为了找到 index节点的位置 从虚拟头节点的下一个节点开始遍历，也就是真实的头节点
        Node cur = dummyHead.next;
        for (int i = 0;i<index;i++){
            cur = cur.next;
        }
        return cur.e;
    }

    /** 获得链表的第一个元素 */
    public E getFirst(){
          return get(0);
    }
    /** 获得链表的最后一个元素 */
    public E getLast(){
          return get(size-1);
    }

    /** 更新index位置的元素 */
    public void set(int index,E e){
          //先判断参数合法性
          if( index <0 || index > size){
              throw new IllegalArgumentException("Update failed,Illegal index!");
          }

          Node cur = dummyHead.next;
          for (int i = 0; i<index;i++){
              cur = cur.next;
          }
          cur.e = e;
    }

    /** 查找链表中是否存在元素e */
    public boolean contains(E e){

          Node cur = dummyHead.next;
          while (cur != null){
              if (cur.e .equals(e)){
                  return true;
              }
              cur = cur.next;
          }
          return false;
    }

    /** 删除元素 删除index位置的元素*/
    public E remove(int index){

          if(index <0 || index>size){
               throw new IllegalArgumentException("Remove failed,index is Illegal!");
          }
          // 寻找待删除元素之前的元素 从虚拟头节点开始遍历
          Node prev = dummyHead;
          for (int i = 0;i<index;i++){
              prev = prev.next;
          }
          Node retNode = prev.next;
          prev.next = retNode.next;
          // 方便垃圾回收
          retNode.next = null;
          //维护Size
          size--;

          return retNode.e;
    }

    /** 删除链表中的第一个元素 */
    public E removeFirst(){
          return remove(0);
    }
    /** 删除链表中的最后一个元素*/
    public E removeLast(){
          return remove(size-1);
    }

    /**  删除链表中的特定元素e */
    public void removeElements(E e){

        Node prev = dummyHead;
        while (prev.next != null){
            if (prev.next.e.equals(e)){
                break;
            }
            prev = prev.next;
        }
        if (prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
        }
    }


    @Override
    public String toString(){

          StringBuilder res = new StringBuilder();
/**           Node cur = dummyHead.next;
        while (cur != null){
              res.append(cur + "->");
              cur = cur.next;
          }*/
          for (Node cur = dummyHead.next;cur !=null;cur = cur.next ){
              res.append(cur + "->");
          }
          res.append("NULL");
          return res.toString();
    }



}
